package com.gavin.algorithm.sort;

import java.util.Arrays;

/**
 * 希尔排序
 * @author Administrator
 *
 */
public class ShellSort {
	
	public static void main(String[] args) {
		int[] a = { 26, 53, 67, 48, 57, 13, 48, 32, 60, 50 };
		shellSort(a);
		System.out.println(Arrays.toString(a));
	}
	
	private static void shellSort(int[] array) {
		int i,j,gap=array.length,temp;
		do {
			gap=gap/3+1;
			
			for(i=gap;i<array.length;i++) {
				if(array[i]>=array[i-gap]) {
					continue;
				}
				
				temp=array[i];
				for(j=i-gap;j>=0&&array[j]>temp;j-=gap) {
					array[j+gap]=array[j];
				}
				array[j+gap]=temp;
			}
			
		}while(gap>1);
	}
}
